package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class LeetCode_day13 {

	public static ListNode mergeTwoSortedLists(ListNode head1, ListNode head2){
		if(head1 == null) return head2;
        if(head2 == null) return head1;
        
        
        
        ListNode newHead = head1.val.doubleValue() < head2.val.doubleValue() ? head1 : head2;
        ListNode indNew = newHead;
        
        ListNode ind1 = head1.next, ind2 = head2.next;
        
        while(ind1 != null || ind2 != null){
            if(ind1 == null){
                indNew.next = ind2;
                ind2 = ind2.next;
                continue;
            }
            
            if(ind2 == null){
                indNew.next = ind1;
                ind1 = ind1.next;
                continue;
            }
            
            if(ind1.val.doubleValue() < ind2.val.doubleValue()){
                indNew.next = ind1;
                ind1 = ind1.next;
                indNew = indNew.next;
            }else{
                indNew.next = ind2;
                ind2 = ind2.next;
                indNew = indNew.next;
            }

        }
        
        //indNew.next = null;//tail
        
        return newHead;
	}
	
	/**
	 * Given two binary strings, return their sum (also a binary string).
	 * @param b1
	 * @param b2
	 */
	public static String addBinary(String b1, String b2){
		if(b1 == null || b1.isEmpty()) return b2;
		if(b2 == null || b2.isEmpty()) return b1;
		
		char[] c1 = b1.toCharArray();
		char[] c2 = b2.toCharArray();
		int ind1 = c1.length - 1, ind2 = c2.length - 1;
		char remain = 0;
		
		LinkedList<Character> result = new LinkedList<Character>();
		while(ind1 >= 0 || ind2 >= 0){
			if(ind1 < 0){
				for(int i = ind2 ; i >= 0 ; i--){
					char[] res = binaryPlus(remain, c2[i]);
					result.add(0,res[0]);
					remain = res[1];
				}
				break;
			}
			
			if(ind2 < 0){
				for(int i = ind1 ; i >= 0 ; i--){
					char[] res = binaryPlus(remain, c1[i]);
					result.add(0,res[0]);
					remain = res[1];
				}
				break;
			}
			
			char[] res = binaryPlus(c1[ind1++], c2[ind2++]);
			result.add(0,res[0]);
			remain = res[1];
		}
		
		return String.valueOf(result.toArray(new Character[result.size()]));
	}
	
	public static char[] binaryPlus(char ch1, char ch2){
		char[] result = new char[2];
		if(ch1 == '1' && ch2 == '1'){
			result[0] = '0'; result[1] = '1';
		}else if(ch1 == '1' || ch2 == '1'){
			result[0] = '1'; result[1] = '0';
		}else{
			result[0] = '0'; result[1] = '0';
		}
		return result;
	}
	
	public static boolean validNumber(String s){
		if(s == null || s.isEmpty()) return false;
		if(s.matches("\\d+(\\.\\d+)?") && s.charAt(0) != '0') return true;
		else if(s.matches("[1-9](\\.\\d+)[e-]10")) return true;//scientific notation
		
		return false;
	}
	
	/**
	 * Given a number represented as an array of digits, plus one to the number.
	 * @param a
	 * @return
	 */
	public static String plusOne(char[] a){
		if(a == null || a.length < 1) return null;
		int sum = Character.getNumericValue(a[a.length-1])+1;
		int remain = sum / 10;
		StringBuilder sb = new StringBuilder(String.valueOf(a));
		sb.replace(sb.length()-1, sb.length()-1, (sum % 10)+"");
		int offset = sb.length()-2;
		while(remain != 0){
			sum = remain + Character.getNumericValue(sb.charAt(offset));
			remain = sum / 10;
			sb.replace(offset, offset, (sum % 10)+"");
			offset--;
			if(offset == -1){
				sb.insert(0, remain);
				break;
			}
		}
		return sb.toString();
	}
	
	/**
	 * !Given an array of words and a length L, 
	 * format the text such that each line has exactly L characters and 
	 * is fully (left and right) justified.
	 * You should pack your words in a greedy approach; 
	 * that is, pack as many words as you can in each line. 
	 * Pad extra spaces ' ' when necessary so that each line has exactly L characters.
	 * Extra spaces between words should be distributed as evenly as possible. 
	 * If the number of spaces on a line do not divide evenly between words, 
	 * the empty slots on the left will be assigned more spaces than the slots on the right.
	 * For the last line of text, it should be left justified and 
	 * no extra space is inserted between words.
	 * 
	 * For example,
	 * words: ["This", "is", "an", "example", "of", "text", "justification."]
	 * L: 16.
	 * Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

     * Analysis:
     * It's a greedy approach.
	 * @param words
	 * @param L
	 */
	public static void textJustification(String[] words, int L){
		if(words == null || L < 1) return;
		List<Line> lines = new ArrayList<Line>();
		Line line = new Line(L);
		int ind = 0;
		while(ind < words.length){
			if(line.addWord(words[ind])) ind++;
			else{
				lines.add(line);
				line = new Line(L);
			}
		}
		lines.add(line);
		
		for(int i = 0 ; i < lines.size() ; i++){
			System.out.println(lines.get(i).toString());
		}		
	}

	/**
	 * Binary search
	 * 二分法？因为sqrt是单调函数
	 * Square root of a (non-negative) number N always lies between 0 and N/2
	 * if the result is k, we have k^2 <= N && (k+1)^2 > N
	 * we set low to represent k and high represent k+1
	 * O(lg n)
	 * @param x
	 * @return
	 */
	public static int sqrtX(int x){
		if(x <= 0) return 0;
		if(x == 1) return 1;
		int high = x / 2 + 1;
		int low = 0;
		while(high > low + 1){
			long mid = low + (high-low)/2;
			if(mid * mid <= x) low = (int)mid;
			else high = (int)mid;
		}
		
		return low;
	}
	/**
	 * Use Newton's method:
	 * x: f(x) = 0
	 * x_{k+1} = x_n - f(x_n) / f'(x_n)
	 * 
	 * here: x^2 = n
	 *       f(x) = x^2 - n
	 * 		 f'(x) = 2x
	 * x - f(x) / f'(x) = 1/2(x + n/x)
	 * 
	 * x_{k+1} = 0.5 (x_k + n / x_k)
	 * @param x
	 * @return
	 */
	public static int sqrtX1(int x){
		if(x == 0) return 0;
		if(x == 1) return 1;
		double x0 = 1;
		double x1;
		while(true){
			x1 = (x0 + x / x0) / 2;
			if(Math.abs(x1-x0) < 1) return (int)x1;
			x0 = x1;
		}
				
	}
	/**
	 * You are climbing a stair case. It takes n steps to reach to the top.
	 * Each time you can either climb 1 or 2 steps. 
	 * In how many distinct ways can you climb to the top?
	 * @param n
	 */
	public static void climbingStairs(int step, List<Boolean> path, List<List<Boolean>> pathes){
		if(step == 0) {
			pathes.add(path);
			return;
		}else{
			List<Boolean> path1 = new ArrayList<Boolean>(path);
			path1.add(true);
			climbingStairs(step-1, path1, pathes);
			if(step >= 2){
				List<Boolean> path2 = new ArrayList<Boolean>(path);
				path2.add(false);
				climbingStairs(step-2, path2, pathes);
			}
		}
	}
	
	/**
	 * !Given an absolute path for a file (Unix-style), simplify it.
	 * For example,
	 * path = "/home/", => "/home"
	 * path = "/a/./b/../../c/", => "/c"
	 * 
	 * Corner Cases:
	 * Did you consider the case where path = "/../"?
	 * In this case, you should return "/".
	 * Another corner case is the path might contain multiple 
	 * slashes '/' together, such as "/home//foo/".
	 * In this case, you should ignore redundant slashes and return "/home/foo".
	 * 
	 * @param path
	 * @return
	 */
	public static String simplifyPath(String path){
		if(path == null) return null;
		String[] strs = path.split("/");
	
		Stack<String> dir = new Stack<String>();
		for(int i = 0 ; i < strs.length ; i++){
			if(strs[i] == "." || strs[i].matches("\\s+")) continue;
			else if(strs[i] == "..") dir.pop();
			else dir.push(strs[i]);
		}
		StringBuilder res = new StringBuilder();
		if(dir.size() != 0){
			Iterator<String> iterator = dir.iterator();
			while(iterator.hasNext()){                        
				res.append("/" + iterator.next());
			}
		}else res.append("/");
		
		return res.toString();
	}
	
	/**
	 * !Given two words word1 and word2, 
	 * find the minimum number of steps required to convert word1 to word2. 
	 * (each operation is counted as 1 step.)
	 * You have the following 3 operations permitted on a word:
	 * a) Insert a character
	 * b) Delete a character
	 * c) Replace a character
	 * 
	 * d('', '') = 0
	 * d(s,'') = d('',s) = |s|
	 * d(s1+ch1, s2+ch2)
	 * 	= min (d(s1, s2)     + if(ch1=ch2) then 0 else 1,
	 * 		   d(s1+ch1, s2) + 1,
	 * 		   d(s1, s2+ch2) + 1).
	 * 
	 * 
	 * @param word1
	 * @param word2
	 */
	public static void editDistance(String word1, String word2){
		
	}
	
	/**
	 * Given a m x n matrix, if an element is 0, set its entire row and column to 0. 
	 * Do it in place.
	 * 常数空间的话，第一可以考虑是不是固定数量的几个变量能搞定；
	 * 否则可以考虑是不是问题本身已经提供了足够的空间。
	 * 这道题属于后者，就是利用矩阵的第一行和第一列来作为辅助空间使用。不用开辟新的存储空间。方法就是：
	 * 1.先确定第一行和第一列是否需要清零
	 * 即，看看第一行中是否有0，记下来。也同时记下来第一列中有没有0。
	 * 2.扫描剩下的矩阵元素，如果遇到了0，就将对应的第一行和第一列上的元素赋值为0
	 * 这里不用担心会将本来第一行或第一列的1改成了0，因为这些值最后注定要成为0的。
	 * 3.根据第一行和第一列的信息，已经可以将剩下的矩阵元素赋值为结果所需的值了
	 * 即，拿第一行为例，如果扫描到一个0，就将这一列都清0.
	 * 4.根据1中确定的状态，处理第一行和第一列。
	 * 如果最开始得到的第一行中有0的话，就整行清零。同理对列进行处理。
	 */
	public static void setMatrixZeroes(int[][] matrix){
		if(matrix == null) return;
		int m = matrix.length , n = matrix[0].length;
		boolean[] hasZero = new boolean[2];
		for(int i = 0 ; i < m ; i++)//for first column 
			if(matrix[i][0] == 0) {
				hasZero[0] = true;
				break;
			}
		for(int i = 0 ; i < n ; i++) //for first row
			if(matrix[0][i] == 0){
				hasZero[1] = true;
				break;
			}
		
		for(int i = 1 ; i < m ; i++) //for other columns and rows
			for(int j = 1 ; j < n ; j++)
				if(matrix[i][j] == 0){
					matrix[i][0] = 0;
					matrix[0][j] = 0;
				}
			
		for(int i = 0 ; i < m ; i++)
			if(matrix[i][0] == 0){
				for(int j = 0 ; j < n ; j++)
					matrix[i][j] = 0;
			}
		
		for(int j = 0 ; j < n ; j++)
			if(matrix[0][j] == 0)
				for(int i = 0 ; i < m ; i++)
					matrix[i][j] = 0;
		if(hasZero[0])
			for(int i = 0 ; i < m ; i++)
				matrix[i][0] = 0;
		if(hasZero[1])
			for(int i = 0 ; i < n ; i++)
				matrix[0][i] = 0;
	}
	
	public static int[] searchA2DMatrix(int[][] matrix , int target){
		if(matrix == null) return null;
		int m = matrix.length;
		int n = matrix[0].length;
		int[] res = new int[2]; res[0] = -2; res[1] = -2;
		
		for(int i = 0 ; i < m ; i++){
			if(matrix[i][0] == target){
				res[0] = i; res[1] = 0; return res;
			}
			if(matrix[i][0] > target) {
				res[0] = i-1; break;
			}
		}
		if(res[0] == -1) return null;
		else if(res[0] == -2) res[0] = m-1;
		
		for(int i = 1 ; i < n ; i++) 
			if(matrix[res[0]][i] == target){
				res[1] = i; return res;
			}
		
		return null;
	}
	
	public static void main(String[] args) {
		textJustification(new String[]{"This", "is", "an", "example", "of", "text", "justification."}, 16);
		System.out.println(sqrtX(Integer.MAX_VALUE));
		System.out.println((3-1)>>1);
		System.out.println(sqrtX1(Integer.MAX_VALUE));
	}

}

class Line{
	List<String> words;
	private int wordsSpace;
	private int totalSpace;
	
	public Line(int L){
		words = new ArrayList<String>();
		wordsSpace = 0;
		totalSpace = L;
	}
	
	public boolean addWord(String word){
		if(totalSpace - wordsSpace - words.size() >= word.length()){
			words.add(word);
			wordsSpace += word.length();
			return true;
		}else return false;
	}
	
	public String toString(){
		//calculating the space between words
		StringBuilder res = new StringBuilder(totalSpace);
		if(words.size() == 1){
			res.append(words.get(0));
			for(int i = totalSpace - wordsSpace ; i > 0 ; i--) res.append(" ");
			return res.toString();
		}
		int nonSpace = totalSpace - wordsSpace;
		int residue = nonSpace % (words.size()-1);
		int spaceNum = nonSpace / (words.size()-1);
		
		
		for(int i = 0 ; i < words.size(); i++){
			res.append(words.get(i));
			if(i != words.size()-1){
				for(int j = 0 ; j < spaceNum ; j++)
					res.append(" ");
				if(i+1 <= residue) res.append(" ");
			}
		}
		return res.toString();
	}
}
